package year2024.month4;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.sql.Array;
import java.util.*;

public class Trap {

    /**
     * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，
     * 可以接 6 个单位的雨水（蓝色部分表示雨水）。
     */
    @Test
    void test1() {

        Assertions.assertEquals(6, trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    @Test
    void test2() {

        Assertions.assertEquals(9, trap(new int[]{4, 2, 0, 3, 2, 5}));
    }

    /**
     * 这一题我觉得我是对的，结果就应该是27，可以用excel画图验证
     */
    @Test
    void test3() {

        Assertions.assertEquals(23, trap(new int[]{5,5,1,7,1,1,5,2,7,6}));
    }



    /**
     * 42 接雨水
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，
     * 下雨之后能接多少雨水。
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {

        leftIndexes = new LinkedList<>();
        rightIndexes = new LinkedList<>();


        int sum = 0;

        for (int i = 0; i < height.length; i++) {

            int heightVal = height[i];

            if (heightVal == 0) {
                continue;
            }

            //int leftLowestVal = height[leftIndexes.peek()];
            if (leftIndexes.isEmpty() || heightVal < height[leftIndexes.peek()]) {
                leftIndexes.push(i);
            } else {

                //int rightMaxVal = height[rightIndexes.peek()];
                if (rightIndexes.isEmpty() || heightVal > height[rightIndexes.peek()]) {
                    rightIndexes.push(i);
                } else {

                    LinkedList<Integer> leftIndexesTemp = new LinkedList<>();

                    int rightMaxHeightValPeek = height[rightIndexes.peek()];
                    Iterator<Integer> iterator = leftIndexes.descendingIterator();
                    while ( iterator.hasNext()) {
                        Integer leftIndex = iterator.next();
                        if(height[leftIndex]>rightMaxHeightValPeek){
                            leftIndexesTemp.push(leftIndex);
                        }
                    }

                    for (Integer rightIndex : rightIndexes) {
                        if (height[rightIndex] > heightVal) {
                            leftIndexesTemp.push(rightIndex);
                        }
                    }


                    //Integer maxRightIndex = rightIndexes.peek();
                    sum += calculateSum(height);

                    leftIndexes = leftIndexesTemp;
                    leftIndexes.push(i);
                }
            }
        }

        return sum + calculateSum(height);
    }

    private int calculateSum(int[] height) {
        int sum = 0;
        int leftStart = 0;
        int rightEnd = 0;
        while (!rightIndexes.isEmpty()) {
            rightEnd = rightIndexes.pop();

            if (!leftIndexes.isEmpty()) {
                leftStart = leftIndexes.removeLast();
            }
            int minUp = Math.min(height[leftStart], height[rightEnd]);

            int left_lowest = 0;
            int right_lowest = 0;
            while (!leftIndexes.isEmpty()) {
                int second_left_lowest = height[leftIndexes.getLast()];
                if (second_left_lowest >= minUp) {
                    leftStart = leftIndexes.removeLast();
                    continue;
                }
                left_lowest = second_left_lowest;
                break;
            }
            if (!rightIndexes.isEmpty()) {
                right_lowest = height[rightIndexes.peek()];
            }
            int maxDown = Math.max(left_lowest, right_lowest);

            sum += (minUp - maxDown) * (rightEnd - leftStart - 1);
        }

        while (!leftIndexes.isEmpty()) {

            leftStart = leftIndexes.removeLast();
            int maxUp = height[leftStart];

            int maxDown = 0;
            if (!leftIndexes.isEmpty()) {
                maxDown = height[leftIndexes.getLast()];
            }

            sum += (maxUp - maxDown) * (rightEnd - leftStart - 1);
        }
        return Math.max(sum, 0);
    }

    LinkedList<Integer> leftIndexes;
    LinkedList<Integer> rightIndexes;
}
